During chip logic design, sets of clock signals, i.e., clock sets, are assumed to arrive at all of their latches at the same time by timing analysis. However, this does not happen. There is clock skew. Clock skew is the variation in effective arrival time of the clock signal at different clocked elements. These variations in clock signal arrival time, that is, clock skew, may be due to one or more effects: different threshold voltages, signal propagation delays on wires, and variation in element delays. The time required for signals, such as clock signals, to propagate on wires in MOSFET technologies is not determined by "speed of light" considerations, except for the very shortest of wires. Rather, clock skew is determined by resistivity and capacitance of the wires and parasitic capacitance. Thus it is essential that, during the subsequent physical design, a clock tree that realizes the objective of effectively controlling clock skew be designed.
There are several approaches to realizing substantially simultaneous arrival of clock signals:
1. partition the clock sinks into nets, place sources for these nets, then continue this process until a single source is reached; or PA0 2. design a clock distribution tree, and then partition clock sinks to the outputs of the clock tree; or PA0 3. a mix of the above approaches.
Other delay balancing approaches exist, but they often rely on adding capacitance, resistance, or additional loads, i.e., wire or passive device load, to achieve balance.
One partitioning objective is to create nets with equal delay. Usually, this cannot be completely realized on any net from its source to its sinks, nor on different nets. Delay is a function of many components, but given multiple copies of a single circuit as net sources and nets that are not physically very large, capacitance and wire length are the dominant factors. A second partitioning objective is to reduce clock tree wire length.
Net capacitance is the sum of two components, (1) the gate capacitance of the sinks in the net, and (2) the capacitance of the wire needed to connect the sinks. The total gate capacitance of the sinks at a stage of the clock tree may or may not be known, especially where the earlier stages are a function of the later stages. The wire capacitance needed to interconnect the sinks depends upon the partitioning of the sinks into nets. For critical clocks, the capacitance of each net must meet both an upper bound and a lower bound. For other clocks and for logic repowering trees, only an upper bound need be met.
Current clock trees are very large, having three thousand or more latch sinks. These sinks must be partitioned into nets with fairly low fanouts to keep capacitance as the main delay variable. Thus, many nets must be defined, each typically with up to twenty five or more sinks per net.
The problem is one of given a large number of sinks, for example, three thousand sinks and a large number of nets, for example, two hundred nets, find the minimum wire length solution with every net having substantially equal net loadings within given limits, and possibly with every net having a maximum number of sinks, for example, twenty five or less sinks. Clearly, this problem grows as a factorial. When the number of nets and the number of sinks per net can or must vary (because of different gate capacitances), the problem is larger. Thus, computational performance is a further problem.
One method heretofore used to accomplish this task is simulated annealing. Simulated Annealing is a slow, computation intensive process.